1905E - One-X - CodeForces Solution

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse4,popcnt,abm,mmx,tune=native")
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
 
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vb = vector<bool>;
 
const int N = 1e5 + 5;
const int K = 21;

const ll mod = 998244353;

map<ll, ll> p2;

ll pw(ll x, ll y) {
    if (p2.count(y) > 0) {
        return p2[y];
    }
    if (y == 0) {
        return 1;
    }
    ll k = pw(x, y / 2);
    if (y & 1) {
        return p2[y] = k * k % mod * x % mod;
    } 
    return p2[y] = k * k % mod;
}
 
ll cnt_ways(ll n) {
    if (n == 1) {
        return 1;
    }
    ll l, r;
    l = (n + 1) / 2;
    r = n / 2;
    return (pw(2, l) - 1) * (pw(2, r) - 1) % mod;
}

ll calc(vector<array<ll, 3>> vec) {
    if (vec.empty()) {
        return 0;
    }
    ll ans = 0;
    vector<array<ll, 3>> tmp, new_vec;
    for (auto x: vec) {
        ans = (ans + cnt_ways(x[0]) * x[1] % mod) % mod;
        if (x[0] == 1) {
            continue;
        }
        if (x[0] % 2) {
            tmp.pb({(x[0] + 1) / 2, x[1] * 2 % mod, x[2]});
            tmp.pb({x[0] / 2, (x[1] * 2 + x[2]) % mod, x[2]});
        } else {
            tmp.pb({x[0] / 2, (x[1] * 4 + x[2]) % mod, x[2] * 2 % mod});
        }
    }
    for (auto x: tmp) {
        bool ok = false;
        for (auto &y: new_vec) {
            if (x[0] == y[0]) {
                y[1] = (y[1] + x[1]) % mod;
                y[2] = (y[2] + x[2]) % mod;
                ok = true;
                break;
            }
        }
        if (!ok) {
            new_vec.pb(x);
        }
    }
    return (ans + calc(new_vec)) % mod;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int te;
    cin >> te;
    while (te--) {
        ll n;
        cin >> n;
        ll ans = calc({{n, 1, 1}});
        cout << ans << '\n';
    }
    return 0;
}